import java.util.ArrayList;

public class Dijkstra {

	// Dijkstra's algorithm to find shortest path from s to all other nodes
	public static int [] dijkstra (Graphe G, int s) {
		final int [] pred = new int [G._nbrSommet];  // preceeding node in path
	
		 for (int i=0; i<G._nbrSommet; i++) {
	           pred[i] = -1;
	        }

		for (int i=0; i<G._nbrSommet; i++) 
		{
			final int next = minVertex (G);
			G._sommets.get(next).set_visited(true);

			// The shortest path to next is dist[next] and via pred[next].

			//final int [] n = G.voisins (next);
			for (int j=0; j<G._sommets.get(next)._liste.get_nbVoisin(); j++) 
			{
				final int v = G._sommets.get(next)._liste._list.get(j).get_distance();
				final int d = G._sommets.get(next).get_distance() + v;
				final int ind = G._sommets.get(next)._liste._list.get(j).get_numVoi();
				if (G._sommets.get(G.getIndexSommet(ind)).get_distance() > d) {
					G._sommets.get(G.getIndexSommet(ind)).set_distance(d);
					pred[G.getIndexSommet(ind)] = next;
				}
			}
		}
		return pred;  // (ignore pred[s]==0!)
	}

	
	private static int minVertex (Graphe G) {
		int x = 1000;
		int y = -1;   // graph not connected, or no unvisited vertices
		for (int i=0; i<G._nbrSommet; i++) {
			if (!G._sommets.get(i).is_visited() && G._sommets.get(i).get_distance()<x) {y=i; x=(int)G._sommets.get(i).get_distance();}
		}
		return y;
	}

	public static void printPath (Graphe G, int [] pred, int s, int e) {
		final ArrayList<Integer> path = new ArrayList<Integer>();
		int x = e;
		while (x!=s) {
			path.add (0, G._sommets.get(x).get_numSommet());
			x = pred[x];
		}
		path.add (0, G._sommets.get(s).get_numSommet());
		System.out.println (path);
	}

}